package exp8;

import java.util.Scanner;

public class C2Prime {
	static int dist[];// 每个点到树的距离
	static boolean visit[];// 是否访问
	static int G[][];// 领接矩阵
	static int N;// N个顶点
	static int E;// E条边
	static int path[];// 记录路线
	// 具体执行方法
	public static void prime(int sourcepoint){
		// 初始化路径，其它点默认从源点到达
		for(int i = 1; i <= N; i++){
			path[i] = sourcepoint;
		}
		// 初始化dist，根据sourcepoint
		for(int i = 1; i <= N; i++){
			dist[i] = G[sourcepoint][i];
		}
		// 给源点标记，因为从这个源点出发
		dist[sourcepoint] = 0;// 最小
		path[sourcepoint] = -1;// 源点出发为-1
		// 生成树的边值总和
		int sum = 0;
		// 每次找的最小点
		int minp;
		// 最小边
		int mine;
		// 外层循环是N个点
		for(int i = 1; i <= N; i++){
			minp = -1;
			mine = Integer.MAX_VALUE;
			// 1.循环找出到已生成的树的最小边的点
			for(int j = 1; j <= N; j++){
				// 没有访问过 ,和最小的边
				if(!visit[j] && dist[j] < mine){
					mine = dist[j];
					minp = j;
				}
			}
			// 没找到退出
			if(minp == -1){
				break;
			}
			// 2.标记访问过
			visit[minp] = true;
			// 累计加上边值
			sum += mine;
			// 3.由minp点到其它点来更新dist值，每个点到已有的树的最小值
			for(int j = 1; j <= N; j++){
				// 没有访问过j点并且j点可达
				if(!visit[j] && G[minp][j] != Integer.MAX_VALUE){
					if(G[minp][j] < dist[j]){
						// 更新值
						dist[j] = G[minp][j];
						// 保存路径
						path[j] = minp;
					}
				}
			}
		}
		// 打印总和
		System.out.println("路径总和："+sum);
	}
	// 打印路径
	public static void printPath(int u){
		// 如果是0代表到达起点
		if(path[u] == -1){
			System.out.print("路径："+u+"->");
		}else{
			// 上一层
			printPath(path[u]);
			// 递归结束，打印路径
			System.out.print(u+"->");
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 点，边
		N = sc.nextInt();
		E = sc.nextInt();
		// 初始化
		G = new int[N + 1][N + 1];
		dist = new int[N + 1];
		visit = new boolean[N + 1];
		path = new int[N + 1];
		
		// 图初始化为最大值
		for(int i = 1; i <= N ; i++){
			for(int j = 1; j <= N ; j++){
				G[i][j] = Integer.MAX_VALUE;
			}
		}
		
		int u, v, e;//点u到v点的e边
		for(int i = 0; i < E; i++){
			u = sc.nextInt();
			v = sc.nextInt();
			e = sc.nextInt();
			G[u][v] = e;
			G[v][u] = e;// 无向图
		}
		// prim
		int sourcepoint = 1;// 源点出发
		prime(sourcepoint);// 执行
		
		for(int i = 1; i <= N; i++){
			// 打印路径
			if(sourcepoint != i){
				System.out.print("生成点："+i+"的路径是：");
				printPath(i);
				System.out.println();
			}
		}
		
		sc.close();
	}
}